A set X of partial words over a finite alphabet A is called unavoidable ifevery two-sided infinite word over A has a factor compatible with an element ofX. Unlike the case of a set of words without holes, the problem of decidingwhether or not a given finite set of n partial words over a k-letter alphabetis avoidable is NP-hard, even when we restrict to a set of partial words ofuniform length. So classifying such sets, with parameters k and n, as avoidableor unavoidable becomes an interesting problem. In this paper, we work towardsthis classification problem by investigating the maximum number of holes we canfill in unavoidable sets of partial words of uniform length over an alphabet ofany fixed size, while maintaining the unavoidability property.
展开▼
